package com.gxd.item_38;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
 */
public class Solution {

    private boolean[] visited;

    private List<String> result;

    public String[] permutation(String s) {
        if (s == null || "".equals(s)) {
            return new String[] {};
        }

        int length = s.length();
        visited = new boolean[length];
        result = new ArrayList<>();

        char[] chars = s.toCharArray();
        Arrays.sort(chars);

        StringBuilder sb = new StringBuilder();
        backTrace(chars, 0, length, sb);

        return result.toArray(new String[] {});
    }

    public void backTrace(char[] chars, int i, int n, StringBuilder sb) {
        if (i == n) {
            result.add(sb.toString());
            return;
        }

        for (int j = 0; j < n; j++) {
            if (visited[j] || (j > 0 && chars[j - 1] == chars[j] && !visited[j - 1])) {
                continue;
            }

            visited[j] = true;
            sb.append(chars[j]);
            backTrace(chars, i + 1, n, sb);
            sb.deleteCharAt(sb.length() - 1);
            visited[j] = false;
        }
    }

    public static void main(String[] args) {
        String s = "abc";
        Solution solution = new Solution();
        String[] permutation = solution.permutation(s);
        System.out.println(Arrays.asList(permutation));
    }
}
